home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
BCCAPP.ARJ
/
INDEX.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-09-15
|
18KB
|
929 lines
/*
*
* Index manipulations.
*
* (C) 1990 Vision Software
*
* $Id: index.c 1.2001 91/04/25 15:08:06 pcalvin release $
*
* Comments:
*
* This class provides DATABASE if efficient indexing of the structures.
* It is currently implemented as a disk-based binary search tree. Some
* extensions were required because we are using records instead of pointers
* First off, the implementation has been modified to link the binary tree
* in both directions. Without this, traversing the tree would be an
* extremely ineffecient function.
* Secondly, recError is used as the terminator for nodes. It is also used
* as the "parent" of the root.
*
* Bugs:
*
* Probably, none presently documented.
*
*/
#include <stdhdr.h>
#include <string.h>
#include <stdlib.h>
#include <dbase.h>
/*
* Absolute construction. Follows normal ACCESS construction.
* In addition, we assert that if no records are available the idx
* structure truely reflects this..
*/
INDEX::INDEX(SZ sz,CCH cch) : ACCESS(&idx,sizeof(ITREE)+cch,sz,".inx",fTrue)
{
/*
* Assert there is records available, if not, fill in tree pointers to
* reflect this.
*/
if (!FFirst())
{
idx.recLeft = recError;
idx.recRight = recError;
idx.recNext = recError;
idx.recPrevious = recError;
idx.recParent = recError;
}
}
/*
* Deletes the current index reference from the disk.
* Answers with the next record in the DATABASE, or recError
* if none exist.
* Simplified if the record to delete has an identical key available
*/
REC INDEX::RecDelete()
{
REC recOriginal = RecQuery();
REC recParent = idx.recParent;
REC recLeft = idx.recLeft;
REC recRight = idx.recRight;
REC recPrevious = idx.recPrevious;
REC recAnswer = recError;
/*
* If key has duplicate, just replace entry
*/
if (idx.recNext != recError)
{
REC recReplace = idx.recNext;
/*
* Fixup replacement first.
*/
Verify(FGotoRec(recReplace));
idx.recParent = recParent;
idx.recLeft = recLeft;
idx.recRight = recRight;
idx.recPrevious = recPrevious;
Verify(FSave());
/*
* If we had previous similar key, fix it.
*/
if (FGotoRec(recPrevious))
{
idx.recNext = recReplace;
Verify(FSave());
}
/*
* Now, links to original part of tree
*/
if (FGotoRec(recParent))
{
if (idx.recLeft == recOriginal)
idx.recLeft = recReplace;
else
idx.recRight = recReplace;
Verify(FSave());
}
else
{
Verify(FMakeFirstRec(recReplace));
}
/*
* And the children..
*/
if (FGotoRec(recLeft))
{
idx.recParent = recReplace;
Verify(FSave());
}
if (FGotoRec(recRight))
{
idx.recParent = recReplace;
Verify(FSave());
}
/*
* Where we want to end up
*/
recAnswer = recReplace;
}
else if (FGotoRec(recPrevious))
{
idx.recNext = recError;
recAnswer = RecQuery();
Verify(FSave());
}
else if (idx.recRight != recError)
{
Verify(FGotoRec(idx.recRight));
/*
* If there is a left sub-tree, follow that chain, otherwise
* simply remove delete record from the list..
*/
if (idx.recLeft == recError)
{
recAnswer = RecDeleteRightLinear(recOriginal,recParent,recLeft);
}
else
{
while (FGotoRec(idx.recLeft))
;
recAnswer = RecDeleteRight(recOriginal,recParent,recRight,recLeft);
}
}
else if (idx.recLeft != recError)
{
Verify(FGotoRec(idx.recLeft));
/*
* If there is a right sub-tree, follow that chain. Otherwise
* remove from the list
*/
if (idx.recRight == recError)
{
recAnswer = RecDeleteLeftLinear(recOriginal,recParent,recRight);
}
else
{
while (FGotoRec(idx.recRight))
;
recAnswer = RecDeleteLeft(recOriginal,recParent,recRight,recLeft);
}
}
else
{
if (!FGotoRec(recParent))
{
Verify(FMakeFirstRec(recError));
}
if (idx.recLeft == recOriginal)
idx.recLeft = recError;
else
idx.recRight = recError;
Verify(FSave());
}
/*
* Delete original reference, Leave record pointer
* at new current
*/
Verify(FGotoRec(recOriginal));
Verify(FDelete());
/*
* Tell dBase where to go..
*/
if (FGotoRec(recAnswer))
return (idx.rec);
else
return (recError);
}
/*
* Answers with the first logical record in the DATABASE.
* If there are any records, we simply follow the BST all the way
* to the left. Otherwise, answer with recError
*/
REC INDEX::RecFirst()
{
REC recAnswer = recError;
if (FFirst())
{
/*
* Search for the first record..
*/
while (idx.recLeft != recError)
{
Verify(FGotoRec(idx.recLeft));
}
/*
* Assert we are at the beginning of at list..
*/
while (idx.recPrevious != recError)
{
Verify(FGotoRec(idx.recPrevious));
}
recAnswer = idx.rec;
}
return (recAnswer);
}
/*
* Answers with the last logical record in the DATABASE, recError
* if none exist
*/
REC INDEX::RecLast()
{
REC recAnswer = recError;
if (FFirst())
{
/*
* Search for the last record
*/
while (idx.recRight != recError)
{
Verify(FGotoRec(idx.recRight));
}
/*
* Goto last in list..
*/
while (idx.recNext != recError)
{
Verify(FGotoRec(idx.recNext));
}
recAnswer = idx.rec;
}
return (recAnswer);
}
/*
* Simple?? traversal of this BinarySearchTree. This implementation is
* complicated by the fact that we may not use recusion to store the
* parent of a record.
*
* If there is a duplicate key to follow, answer with that.
*
* Answers with the rec in the DATABASE, or recError
*/
REC INDEX::RecNext()
{
REC recOriginal = RecQuery();
/*
* Check first for a duplicate, if none are found, follow
* recPrevious until we are at the head
*/
if (idx.recNext != recError)
{
Verify(FGotoRec(idx.recNext));
return (idx.rec);
}
else
{
Verify(FFirstInChain());
}
REC rec = idx.recRight;
REC recAnswer = recError;
/*
* Two possibilities at this stage:
* 1. recRight != recError (i.e. Right subtree exists)
* In this case, the next record is the farthest left sub
* tree that exists..
* 2. recRight == recError (i.e. Right subtree does not exist)
* This case has two possibilities:
* 1. Current branch is a left sub-tree
* The next record is the parent of the current record
* 2. Current branch is a right sub-tree
* Follow parent's chain while the child is a right sub-tree
* the next record is the first parent who the child as a left
* sub-tree
*/
if (rec != recError)
{
while (FGotoRec(rec) && idx.recLeft != recError)
rec = idx.recLeft;
recAnswer = idx.rec;
}
else
{
REC recSearchBase = RecQuery();
if (idx.recParent == recError)
{
if (recOriginal != recError)
{
Verify(FGotoRec(recOriginal));
}
recAnswer = recError;
}
else
{
Verify(FGotoRec(idx.recParent));
if (idx.recLeft == recSearchBase)
{
recAnswer = idx.rec;
}
else
{
REC recChild = recSearchBase;
while (idx.recRight == recChild && idx.recParent != recError)
{
recChild = RecQuery();
Verify(FGotoRec(idx.recParent));
}
/*
* Was a left-parent found??
*/
if (idx.recLeft == recChild)
{
recAnswer = idx.rec;
}
else
{
Verify(FGotoRec(recOriginal));
recAnswer = recError;
}
}
}
}
return (recAnswer);
}
/*
* Answers with the previous record in the DATABASE, or recError
*
* If there is a duplicate key previous, answer with that.
*/
REC INDEX::RecPrevious()
{
/*
* Check first for a duplicate, if found, answer with that.
*/
if (idx.recPrevious != recError)
{
Verify(FGotoRec(idx.recPrevious));
return (idx.rec);
}
REC rec = idx.recLeft;
REC recAnswer = recError;
/*
* Two possibilities at this stage:
* 1. recLeft != recError (i.e. Left subtree exists)
* In this case, the previous record is the farthest right
* sub-tree of that record..
* 2. recLeft == recError (i.e. Left subtree does not exist)
* This case as two possibilities:
* 1. Current branch is a right sub-tree
* The parent(if it exists) is the previous one.
* 2. Current branch is a left sub-tree
* Follow the parents chain while the child is a left-subtree
* the previous record is the first parent that has the child as a
* right sub-tree
*/
if (rec != recError)
{
while (FGotoRec(rec) && idx.recRight != recError)
rec = idx.recRight;
Verify(FLastInChain());
recAnswer = idx.rec;
}
else
{
REC recOriginal = RecQuery();
if (idx.recParent == recError)
{
if (recOriginal != recError)
{
Verify(FGotoRec(recOriginal));
}
recAnswer = recError;
}
else
{
Verify(FGotoRec(idx.recParent));
if (idx.recRight == recOriginal)
{
Verify(FLastInChain());
recAnswer = idx.rec;
}
else
{
REC recChild = recOriginal;
while (idx.recLeft == recChild && idx.recParent != recError)
{
recChild = RecQuery();
Verify(FGotoRec(idx.recParent));
}
/*
* Did we find one??
*/
if (idx.recRight == recChild)
{
Verify(FLastInChain());
recAnswer = idx.rec;
}
else
{
Verify(FGotoRec(recOriginal));
recAnswer = recError;
}
}
}
}
return (recAnswer);
}
/*
* Finally!! Something simple. Here we are traversing the BST in search
* of sz.
* Answers with rec in DATABASE or recError if it doesn't exist..
* If fMatchIfClose, we answer with a match only if sz matches
* the key for its' length.
*/
REC INDEX::RecFromSz(SZ sz,CCH cch,BOOL fMatchIfClose)
{
Assert(sz != szNil);
REC recAnswer = recError;
BOOL fContinue = fTrue;
CCH cchCompare = (fMatchIfClose) ? strlen(sz) : cch;
/*
* If sz is not safely formed, assert that the length
* remains less than the maximum
*/
if (cchCompare > cch)
cchCompare = cch;
/*
* Optimization. If we are already at the key, just answer
* Otherwise, if there are no records available, answer
*/
if (strncmp(sz,idx.rgchKey,cchCompare) == 0)
return (idx.rec);
else if (!FFirst())
return (recError);
/*
* Disk-based Binary Search Tree..
*/
while (fContinue)
{
REC recSearch = recError;
DSZ dsz = strncmp(sz,idx.rgchKey,cchCompare);
if (dsz == 0)
{
recAnswer = idx.rec;
fContinue = fFalse;
}
else if (dsz < 0)
{
recSearch = idx.recLeft;
}
else
{
recSearch = idx.recRight;
}
if (fContinue)
fContinue = FGotoRec(recSearch);
}
return (recAnswer);
}
/*
* Creates an index reference for the DATABASE. Simple insertion
* into the BST. Must be sure to recall the parents. Also check
* for inserting if there are no records. (The ROOT)
*/
REC INDEX::RecCreateSz(SZ sz,CCH cchCompare,REC recCreated)
{
Assert(sz != szNil);
REC recAnswer = recError;
REC recIndex = recError;
BOOL fContinue = fTrue;
/*
* If this is the first record in the tree, just create it..
* Be sure to tell ACCESS() that this is the root of the tree.
*/
if (!FFirst())
{
recIndex = RecFromSzCchRecRec(sz,cchCompare,recCreated,recError);
Verify(FMakeFirstRec(recIndex));
fContinue = fFalse;
recAnswer = recCreated;
}
/*
* Disk-based Binary Search Tree..
*/
while (fContinue)
{
DSZ dsz = strncmp(sz,idx.rgchKey,cchCompare);
/*
* If identical, Create the new record at the end of the chain.
* Otherwise, continue search.
*/
if (dsz == 0)
{
recIndex = RecCreateDuplicate(sz,cchCompare,recCreated);
recAnswer = recCreated;
fContinue = fFalse;
}
else if (dsz < 0)
{
/*
* Found end of BST. Add new record into the INDEX
*/
if (idx.recLeft == recError)
{
REC rec = RecQuery();
recIndex = RecFromSzCchRecRec(sz,cchCompare,recCreated,rec);
Verify(FGotoRec(rec));
idx.recLeft = recIndex;
Verify(FSave());
recAnswer = recCreated;
fContinue = fFalse;
}
else
{
Verify(FGotoRec(idx.recLeft));
}
}
else
{
/*
* Found end of BST. New record is placed here..
*/
if (idx.recRight == recError)
{
REC rec = RecQuery();
recIndex = RecFromSzCchRecRec(sz,cchCompare,recCreated,rec);
Verify(FGotoRec(rec));
idx.recRight = recIndex;
Verify(FSave());
recAnswer = recCreated;
fContinue = fFalse;
}
else
{
Verify(FGotoRec(idx.recRight));
}
}
}
/*
* Assure that we leave the index file pointing to the
* current record
*/
Verify(FGotoRec(recIndex));
return (recAnswer);
}
/*
* This function places a new record at the end of the chain.
* Answers with the created record.
*/
REC INDEX::RecCreateDuplicate(SZ sz,CCH cch,REC recCreated)
{
/*
* Follow chain..
*/
while (idx.recNext != recError)
Verify(FGotoRec(idx.recNext));
/*
* For identical chains, this is simply a linked list..
*/
REC recPrevious = RecQuery();
REC recNext = RecFromSzCchRecRec(sz,cch,recCreated,recError);
/*
* Now, both links have been created, join them..
*/
Verify(FGotoRec(recNext));
idx.recPrevious = recPrevious;
Verify(FSave());
Verify(FGotoRec(recPrevious));
idx.recNext = recNext;
Verify(FSave());
return (recNext);
}
/*
* Creates a new record and copies the index entry and DATABASE destination
* to it..
*/
REC INDEX::RecFromSzCchRecRec(SZ sz,CCH cch,REC recCreated,REC recParent)
{
REC recIndex = RecCreate();
strncpy(idx.rgchKey,sz,cch);
idx.rec = recCreated;
idx.recLeft = recError;
idx.recRight = recError;
idx.recPrevious = recError;
idx.recNext = recError;
idx.recParent = recParent;
Verify(FSave());
return (recIndex);
}
/*
* Deletes an entry from the Binary Search Tree. In this case, we
* are deleting from a list
*/
REC INDEX::RecDeleteRightLinear(REC recOriginal,REC recParent,REC recLeft)
{
REC recReplace = RecQuery();
idx.recParent = recParent;
idx.recLeft = recLeft;
idx.recNext = recError;
idx.recPrevious = recError;
Verify(FSave());
if (FGotoRec(recLeft))
{
idx.recParent = recReplace;
Verify(FSave());
}
if (!FGotoRec(recParent))
{
Verify(FMakeFirstRec(recReplace));
}
else
{
if (idx.recLeft == recOriginal)
idx.recLeft = recReplace;
else
idx.recRight = recReplace;
Verify(FSave());
}
return (recReplace);
}
/*
* Deletes an entry from the left line..
*/
REC INDEX::RecDeleteLeftLinear(REC recOriginal,REC recParent,REC recRight)
{
REC recReplace = RecQuery();
idx.recParent = recParent;
idx.recRight = recRight;
idx.recNext = recError;
idx.recPrevious = recError;
Verify(FSave());
if (FGotoRec(recRight))
{
idx.recParent = recReplace;
Verify(FSave());
}
if (!FGotoRec(recParent))
{
Verify(FMakeFirstRec(recReplace));
}
else
{
if (idx.recLeft == recOriginal)
idx.recLeft = recReplace;
else
idx.recRight = recReplace;
Verify(FSave());
}
return (recReplace);
}
/*
* Deletes an entry that doesn't fall in a linear list..
*/
REC INDEX::RecDeleteRight(REC recOriginal,REC recParent,REC recRight,REC recLeft)
{
REC recReplace = RecQuery();
REC recReplaceParent = idx.recParent;
REC recReplaceRight = idx.recRight;
/*
* Step #1
*/
Verify(FGotoRec(recReplaceParent));
idx.recLeft = recReplaceRight;
Verify(FSave());
if (FGotoRec(recReplaceRight))
{
idx.recParent = recReplaceParent;
Verify(FSave());
}
/*
* Step #2
*/
if (!FGotoRec(recParent))
{
Verify(FMakeFirstRec(recReplace));
}
else
{
if (idx.recLeft == recOriginal)
idx.recLeft = recReplace;
else
idx.recRight = recReplace;
Verify(FSave());
}
/*
* Step #3
*/
if (FGotoRec(recRight))
{
idx.recParent = recReplace;
Verify(FSave());
}
if (FGotoRec(recLeft))
{
idx.recParent = recReplace;
Verify(FSave());
}
/*
* Step #4
*/
Verify(FGotoRec(recReplace));
idx.recParent = recParent;
idx.recRight = recRight;
idx.recLeft = recLeft;
idx.recNext = recError;
idx.recPrevious = recError;
Verify(FSave());
return (recReplace);
}
/*
* Deletes an entry that doesn't fall in a linear list..
*/
REC INDEX::RecDeleteLeft(REC recOriginal,REC recParent,REC recRight,REC recLeft)
{
REC recReplace = RecQuery();
REC recReplaceParent = idx.recParent;
REC recReplaceLeft= idx.recLeft;
/*
* Step #1
*/
Verify(FGotoRec(recReplaceParent));
idx.recRight = recReplaceLeft;
Verify(FSave());
if (FGotoRec(recReplaceLeft))
{
idx.recParent = recReplaceParent;
Verify(FSave());
}
/*
* Step #2
*/
if (!FGotoRec(recParent))
{
Verify(FMakeFirstRec(recReplace));
}
else
{
if (idx.recLeft == recOriginal)
idx.recLeft = recReplace;
else
idx.recRight = recReplace;
Verify(FSave());
}
/*
* Step #3
*/
if (FGotoRec(recLeft))
{
idx.recParent = recReplace;
Verify(FSave());
}
if (FGotoRec(recRight))
{
idx.recParent = recReplace;
Verify(FSave());
}
/*
* Step #4
*/
Verify(FGotoRec(recReplace));
idx.recParent = recParent;
idx.recRight = recRight;
idx.recLeft = recLeft;
idx.recNext = recError;
idx.recPrevious = recError;
Verify(FSave());
return (recReplace);
}
/*
* These functions allow use to move back and forth throughout a duplicate
* key
*/
BOOL INDEX::FLastInChain()
{
while (idx.recNext != recError)
Verify(FGotoRec(idx.recNext));
return (fTrue);
}
BOOL INDEX::FFirstInChain()
{
while (idx.recPrevious != recError)
Verify(FGotoRec(idx.recPrevious));
return (fTrue);
}